//gcd(F(n),F(m))=F(gcd(n,m))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e8+9;
const ll MOD=1e8;
ll F[N];
ll gcd(ll n,ll m){
    if(n%m==0) return m;
    return gcd(m,n%m);
}
int main(){
    ll n,m;
    cin>>n>>m;
    ll g=gcd(n,m);
    if(g<3){
        cout<<1<<endl;
        return 0;
    }
    F[1]=F[2]=1;
    for(int i=3;i<=g;i++)
        F[i]=(F[i-1]+F[i-2])%MOD;
    cout<<F[g]<<endl;
    return 0;
}